#include <iostream>
using namespace std;

template <class K, class V>
struct BSTreeNode{
  typedef BSTreeNode<K, V> Node;
  Node *_left;
  Node *_right;
  K _key;
  V _val;

  BSTreeNode(const K &key = K(), const V &val = V())
    :_left(nullptr),
    _right(nullptr),
    _key(key),
    _val(val)
  {}
}; 

template <class K, class V>
class BSTree{
public:
  typedef BSTreeNode<K, V> Node;
  BSTree(){}

  BSTree(const BSTree<K, V> &bst){
    _root = _Copy(bst._root);
  }

  BSTree<K,V>& operator=(BSTree<K,V> bst){
    swap(bst._root, _root);
    return *this;
  }
  
  ~BSTree(){
    _Destroy(_root);
  }

  void InOrder(){
    _InOrder(_root);  
    //cout << endl;
  }
  
  bool Insert(const K &key, const V &val);
  
  Node* Find(const K &key);

  bool Erase(const K &key);
  

private:
  Node *_root = nullptr;

  Node* _Copy(Node *root);

  void _Destroy(Node *root);

  void DelNode(Node *parent, Node *cur);

  void _InOrder(Node *root);
};

template <class K, class V>
bool BSTree<K,V>::Insert(const K &key, const V &val){
    if(_root == nullptr)
    {
      _root = new Node(key, val);
      return true;
    }
    Node *cur = _root;
    Node *parent = _root;
    while(cur != nullptr)
    {
      parent = cur;
      if(key > cur->_key)
      {
        cur = cur->_right;
      }
      else if(key < cur->_key)
      {
        cur = cur->_left;
      }
      else{
        return false;
      }
    }
    if(key > parent->_key)
    {
      parent->_right = new Node(key, val);
    }
    else{
      parent->_left = new Node(key, val);
    }
    return true;
}
  
template <class K, class V>
    BSTreeNode<K,V>* BSTree<K,V>::Find(const K &key){
    if(_root == nullptr) return nullptr;
    Node *cur = _root;
    while(cur != nullptr)
    {
      if(key > cur->_key)
      {
        cur = cur->_right;
      }
      else if(key < cur->_key)
      {
        cur = cur->_left;
      }
      else{
        return cur;
      }
    }
    return nullptr;
  }
  
template <class K, class V>
    bool BSTree<K,V>::Erase(const K &key){
    Node *cur = _root;
    Node *parent = _root; 
    while(cur != nullptr)
    {
      if(key > cur->_key)
      {
        parent = cur; //移动cur之前，记录parent。找到了不移动。
        cur = cur->_right;
      }
      else if(key < cur->_key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else{
        if(cur->_left == nullptr || cur->_right == nullptr)
        {
          DelNode(parent, cur);
        }
        else{
          Node *lmaxp = cur; //如果cur->left就是最大值,lmaxp应该指向cur
          Node *lmax = cur->_left;
          while(lmax->_right != nullptr) 
          {
            lmaxp = lmax;
            lmax = lmax->_right;
          } 
          swap(cur->_key, lmax->_key);
          DelNode(lmaxp, lmax);
        }
        return true; //完成删除马上返回
      }
    }
     return false; 
  }

template <class K, class V>
  BSTreeNode<K,V>* BSTree<K,V>::_Copy(Node *root){
    if(root == nullptr) return nullptr;
    Node *copyroot = new Node(root->_key, root->_val);
    copyroot->_left = _Copy(root->_left);
    copyroot->_right = _Copy(root->_right);
    return copyroot;
  }

template <class K, class V>
  void BSTree<K,V>::_Destroy(Node *root){
    if(root == nullptr) return;
    _Destroy(root->_left);
    _Destroy(root->_right);
    delete root;
  } 

template <class K, class V>
  void BSTree<K,V>::DelNode(Node *parent, Node *cur){
    if(cur->_left == nullptr)
    {
      if(cur == _root) //如果要删除的是根节点，需要特殊处理。
      {
        _root = cur->_right;
      }
      else if(parent->_left == cur)
      {
        parent->_left = cur->_right;
      }
      else{
        parent->_right = cur->_right;
      }
    }
    else if(cur->_right == nullptr)
    {
      if(cur == _root)
      {
        _root = cur->_left;
      }
      else if(parent->_left == cur)
      {
        parent->_left = cur->_left;
      }
      else{
        parent->_right = cur->_left;
      }
    }
    delete cur;
  }

template <class K, class V>
  void BSTree<K,V>::_InOrder(Node *root){
    if(root == nullptr) return;
    _InOrder(root->_left);
    cout << root->_key << "-->" << root->_val << endl;
    _InOrder(root->_right);
  }

